package class07;

/**
 * 假设有排成一行的N个位置记为1到NN一定大于等于2
 * 开始时机器人在其中的M位置上M一定是1到N中的一个
 * 如果机器人来到1位置
 * 那么下一步只能往右来到2位置
 * 如果机器人来到N位置那么下一步只能往左来到N-1的位置
 */
public class Code01_RobotWalk {

    /**
     * @param N     长度
     * @param start 起始位置
     * @param aim   目标位置
     * @param K     剩余步数
     * @return
     */
    public static int ways3(int N, int start, int aim, int K) {
        int[][] dp = new int[N + 1][K + 1];
        dp[aim][0] = 1;
        for (int rest = 1; rest <= K; rest++) {
            dp[1][rest] = dp[2][rest - 1];// 直接赋值 cur=1时
            for (int cur = 2; cur < N; cur++) {
                dp[cur][rest] = dp[cur - 1][rest - 1] + dp[cur + 1][rest - 1];
            }
            dp[N][rest] = dp[N - 1][rest - 1];// 直接赋值 cur=N时
        }
        return dp[start][K];
    }

    /**
     * @param N     长度
     * @param start 起始位置
     * @param aim   目标位置
     * @param K     剩余步数
     * @return
     */
    public static int ways2(int N, int start, int aim, int K) {
        if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
            return -1;
        }
        int[][] dp = new int[N + 1][K + 1];
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= K; j++) {
                dp[i][j] = -1;
            }
        }
        return process2(start, K, aim, N, dp);
    }

    static int process2(int cur, int rest, int aim, int n, int[][] dp) {
        int ans = 0;
        if (dp[cur][rest] != -1) {
            return dp[cur][rest];
        }

        if (rest == 0) {
            ans = cur == aim ? 1 : 0;
        } else if (cur == 1) {
            ans = process2(2, rest - 1, aim, n, dp);
        } else if (cur == n) {
            ans = process2(cur - 1, rest - 1, aim, n, dp);
        } else {
            ans = process2(cur - 1, rest - 1, aim, n, dp) + process2(cur + 1, rest - 1, aim, n, dp);
        }

        dp[cur][rest] = ans;
        return ans;
    }

    public static int ways1(int N, int start, int aim, int K) {
        if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
            return -1;
        }
        return process1(start, K, aim, N);
    }

    static int process1(int cur, int rest, int aim, int n) {
        if (rest == 0) {
            return cur == aim ? 1 : 0;
        } else if (cur == 1) {
            return process1(2, rest - 1, aim, n);
        } else if (cur == n) {
            return process1(cur - 1, rest - 1, aim, n);
        } else {
            return process1(cur - 1, rest - 1, aim, n) + process1(cur + 1, rest - 1, aim, n);
        }
    }

    public static void main(String[] args) {
        System.out.println(ways1(5, 2, 4, 6));
        System.out.println(ways2(5, 2, 4, 6));
        System.out.println(ways3(5, 2, 4, 6));
    }
}
